package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.util.*;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/29 11:11
 */
public class JZSolution039 {

    public int largestRectangleArea(int[] heights) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        for (int i = 0; i < heights.length; i++) {
            list.add(heights[i]);
        }
        list.add(0);
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int result = 0;
        for (int i = 0; i < list.size();) {
            if(list.get(stack.peek())<=list.get(i)){
                stack.push(i);
                i++;
            }else {
                Integer pop = stack.pop();
                result = Math.max(result,(i-stack.peek()-1)*list.get(pop));
            }
        }
        return result;
    }

    @Test
    public void test01(){
        int[] heights = {2,1,5,6,2,3};
        int result = largestRectangleArea(heights);
        System.out.println(result);
    }

}
